package 力扣.堆;


import java.util.Arrays;

public class 堆的基础知识 {
    private int[] nums;
    private int n;//n总是在我们'需要操作的元素'的后一位
    public static void main(String[] args) {
        堆的基础知识  heap= new 堆的基础知识();
        heap.nums = new int[]{8, 3, 6, 5, 4, 7};
        heap.n = 5;
//        heap.pop();
        heap.push(10);
        System.out.println(Arrays.toString(heap.nums));

    }

//    堆的基础知识
    public void test(int i){
        //使用数组表示堆
        int[] ints = {1,8,3,6,5,4,7};
        //孩子节点
        int left = i << 1 + 1;
        int right = i << 1 + 2;

        //父节点
        int par = (i - 1) >> 1;
    }

    /**大根堆上浮操作
     * 大根堆上浮贪心原则：我只要比父节点大我就上浮
     */
    public  void rise(int i) {
        int te = nums[i];
        while (i > 0) {//0没有父节点
            int par = (i - 1) >> 1;
            if (nums[par] < te){//贪心原则：只要比父节点大，就上移
                nums[i] = nums[par];//上浮(父节点下沉)
                i = par;
            }else {
                break;
            }
        }
        nums[i] = te;
    }

    /**大根堆下沉操作
     * 大根堆下沉贪心原则：找到最大的子节点，只要比父节点大，父节点就下沉
     */
    public void sink(int i) {
        int te = nums[i];
        int len = nums.length;
        int j = (i << 1) + 1;//孩子节点
        while ( j < len ){
            if (j < len - 1 && nums[j] < nums[j + 1]){//找到最大的孩子节点
                j++;
            }
            //交换
            int son = nums[j];
            if (son > te){
                nums[i] = son;//下沉（子节点上浮）
                i = j;
                j = (i << 1) + 1;
            }else {
                break;
            }
        }
        nums[i] = te;
    }
    /**
     * 大根堆push操作
     * 原理：往堆的尾巴：nums[n]上添加新的元素，然后将nums[n]进行上浮操作
     */
    public  Boolean push(int v) {
        if (n >= nums.length){
            return false;
        }
        nums[n] = v;
        rise(n++);//上浮,n先后移动一位
        return true;
    }
    /**
     * 大根堆pop操作
     * 原理：对堆的头部：nums[0]进行删除，然后将nums[n-1](堆中最后一个值，否则会出现重复元素) 赋值给 nums[0],最后对nums[0] 进行下沉操作
     */
    public  int  pop() {
        int re = nums[0];
        nums[0] = nums[n - 1];
        nums[n-1] = 0;
        sink( 0);
        return re;
    }
}
